\subsection*{Problema y solución}

El objetivo de este problema es simular reemplazos de caracteres en un
string, y calcular la cantidad de apariciones de un caracter determinado
en la cadena transformada. Los datos de entrada son las reglas $Q_i$ a aplicar,
un string $s$ que define la frecuencia inicial de cada caracter, el número de
veces $n$ a aplicar las reglas y el caracter $c$ del que se desea conocer su
frecuencia.

Por obvias razones de eficiencia no ejecutamos los reemplazos sobre el
string dado, sino que los simulamos guardando en una matriz la frecuencia
de cada caracter. Esta matriz contiene inicialmente las frecuencias con
que aporta cada caracter según las reglas, y tiene la propiedad de que,
al multiplicarla por sí misma (con algunos cuidados, detallados a
continuación) mantiene las frecuencias de haber aplicado una vez las
reglas dadas sobre el string.

Si hay caracteres en el string que no dan inicio a reglas, algunas filas de
la matriz quedarán nulas, lo que puede redundar en pérdidas de información al
hacer las multiplicaciones. Es fácil ver, en el ejemplo anterior, que $M=M^n\
\forall\ n$. Dado que el enunciado indica que todo caracter que no aparece en
una regla se mantiene, podría mantenerse la diagonal en 1 como implementación
de dicha identidad. Pero por la forma en que calculamos la frecuencia nos fue
conveniente modificar levemente la multiplicación de matrices para que
mantenga los datos necesarios. Procedemos de la siguiente manera: antes de
reemplazar el valor de $M_{ij}$ chequeamos si $j$ es un caracter que da
inicio a reglas (mediante el vector {\tt in\_queries}). En ese caso, se
reemplaza $M_{ij}$ normalmente y se continúa la multiplicación; en caso
contrario, en lugar de reemplazarlo, se suma el nuevo valor al que contenía
dicha celda. De esta manera se lleva cuenta del agregado de caracteres aunque
la fila correspondiente sea nula.

Así, para el caso de ejemplo $A \rightarrow BAcX$, y dado el string de inicio
$ABCcXA$, ejemplos de matriz serán:

$$M =
\begin{array}{l}
\begin{matrix}
	\ \ A & B & C & X & c
\end{matrix} \\
\left(
	\begin{array}{ccccc}
	1 & 1 & 0 & 1 & 1 \\
	0 & 0 & 0 & 0 & 0 \\
	0 & 0 & 0 & 0 & 0 \\
	0 & 0 & 0 & 0 & 0 \\
	0 & 0 & 0 & 0 & 0 \\
	\end{array}
\right)
\hspace{1cm}
M^2 = \left(
\begin{array}{ccccc}
1 & 2 & 0 & 2 & 2 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
\end{array}
\right)
\hspace{1cm}
M^3 = \left(
\begin{array}{ccccc}
1 & 3 & 0 & 3 & 3 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
\end{array}
\right)
\end{array}
$$

Cada valor $M_{ij}^k$ representa la cantidad de caracteres $`j'$ que incorpora
el caracter $`i'$ en la $k$-ésima aplicación de reglas. La frecuencia
de un caracter $c$ luego de $n$ aplicaciones de reglas sobre una cadena $str$
(la respuesta al problema) resulta ser:
$$\sum_i M_{ic}^n \times cant\_apariciones(str, c)$$


\subsection*{Detalles de Implementación}

Dado que los valores se encuentran entre los números 33 y 126 de la tabla ASCII,
armamos matrices de dimensión $94\times 94$, que representan a todos los valores
de entrada posibles. Al direccionar caracteres en la matriz restamos un {\sl offset}
de 33 a su valor ASCII.

Utilizamos el tipo de datos {\tt unsigned long long int} para las matrices y
el valor de frecuencia.


\subsection*{Análisis de complejidad}

Para calcular $M^e$ utilizamos el algoritmo de exponenciación binaria, basado en
que $x^e = (x^\frac e 2)^2$ (si $e$ es par), disminuyendo la cantidad de
multiplicaciones en forma logarítmica respecto del valor del exponente. Así, la
multiplicación de matrices (algoritmo de orden $N^3$, siendo $N$
la cantidad de columnas) se ejecuta $O(\log e)$ veces.

Rellenar la matriz con las $N$ {\sl queries} toma $O(N^3)$, y calcular la suma
final de frecuencias toma $O(N)$, por lo que la complejidad total resulta de
$O(N^3\log e + N)$.
